<html>
<head><meta charset="utf-8"><title>Iteration order for dataflow · t-compiler · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/index.html">t-compiler</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html">Iteration order for dataflow</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="168761069"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168761069" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168761069">(Jun 22 2019 at 18:48)</a>:</h4>
<p>At the moment, dataflow iteration begins processing blocks in order of ascending IDs (<code>BasicBlock(0)</code>, <code>BasicBlock(1)</code>, etc.). However, for maximum efficiency during <em>forward</em> dataflow, basic blocks should be processed in reverse post-order. My guess is that the current ID ordering is pretty close to RPO for most functions, but it might be worth doing a perf run anyways.</p>
<p>Additionally, there is currently a <em>backward</em> dataflow analysis for liveness which is also iterating over blocks in order of ascending IDs. I think this could be sped up by initializing the <code>WorkQueue</code> in postorder (or alternatively reverse post-order on the reverse CFG).</p>



<a name="168761146"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168761146" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168761146">(Jun 22 2019 at 18:51)</a>:</h4>
<p>Does anyone have an opinion on whether this is worth pursuing? The implementation is pretty simple, I would just need someone to trigger a perf run.</p>



<a name="168762355"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168762355" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168762355">(Jun 22 2019 at 19:29)</a>:</h4>
<p>Worth doing, yes.</p>



<a name="168762492"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168762492" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168762492">(Jun 22 2019 at 19:33)</a>:</h4>
<p><span class="user-mention" data-user-id="123586">@nagisa</span>, should I open an issue for this as well to solicit discussion? Or just a PR?</p>



<a name="168762549"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168762549" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168762549">(Jun 22 2019 at 19:35)</a>:</h4>
<p>PR is sufficient.</p>



<a name="168762777"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168762777" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168762777">(Jun 22 2019 at 19:42)</a>:</h4>
<p>Okay, I think I'll do the forward and reverse cases separately.</p>



<a name="168762812"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168762812" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168762812">(Jun 22 2019 at 19:43)</a>:</h4>
<p>That way they can get benchmarked independently</p>



<a name="168763844"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168763844" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168763844">(Jun 22 2019 at 20:16)</a>:</h4>
<p>Forward is <a href="https://github.com/rust-lang/rust/issues/62062" target="_blank" title="https://github.com/rust-lang/rust/issues/62062">#62062</a></p>



<a name="168764778"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168764778" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168764778">(Jun 22 2019 at 20:48)</a>:</h4>
<p>Reverse is <a href="https://github.com/rust-lang/rust/issues/62063" target="_blank" title="https://github.com/rust-lang/rust/issues/62063">#62063</a></p>



<a name="168765085"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168765085" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168765085">(Jun 22 2019 at 20:59)</a>:</h4>
<p><span class="user-mention" data-user-id="123586">@nagisa</span> bors failed for <a href="https://github.com/rust-lang/rust/issues/62062" target="_blank" title="https://github.com/rust-lang/rust/issues/62062">#62062</a>. Both PRs include a change to the API for <code>WorkQueue</code> since I assumed they both had to be based on <code>master</code>.</p>



<a name="168765086"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168765086" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168765086">(Jun 22 2019 at 20:59)</a>:</h4>
<p>How should I proceed?</p>



<a name="168765147"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168765147" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168765147">(Jun 22 2019 at 21:01)</a>:</h4>
<p>They both should be independently based on master, yes. This looks like an unrelated failure to me.</p>



<a name="168765148"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168765148" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168765148">(Jun 22 2019 at 21:01)</a>:</h4>
<p>Ah, okay</p>



<a name="168766582"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168766582" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168766582">(Jun 22 2019 at 21:50)</a>:</h4>
<p><span class="user-mention" data-user-id="123586">@nagisa</span> Some tests failed since there were unreachable basic blocks in the <code>mir::Body</code>. The easiest way to preserve the original behavior is to re-add all basic-block indexes after doing traversal, which will pick up any unreachable ones. A further optimization might be to add a dead block elimination pass that gets run before dataflow, but that is probably outside the scope of this PR.</p>



<a name="168802541"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168802541" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168802541">(Jun 23 2019 at 18:02)</a>:</h4>
<p>Results are in for forward analysis: <a href="https://perf.rust-lang.org/compare.html?start=d6884aedd5b8709c44c849d055d454db2f78042e&amp;end=0905d6a630cb4afc3f894f9e91c1a7a20c32416b" target="_blank" title="https://perf.rust-lang.org/compare.html?start=d6884aedd5b8709c44c849d055d454db2f78042e&amp;end=0905d6a630cb4afc3f894f9e91c1a7a20c32416b">https://perf.rust-lang.org/compare.html?start=d6884aedd5b8709c44c849d055d454db2f78042e&amp;end=0905d6a630cb4afc3f894f9e91c1a7a20c32416b</a></p>



<a name="168802615"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168802615" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168802615">(Jun 23 2019 at 18:04)</a>:</h4>
<p>Seems pretty <span aria-label="shrug" class="emoji emoji-1f937" role="img" title="shrug">:shrug:</span> to me? This suggests that either forward dataflow is a small component of perf, or that basic block ordering is pretty close to RPO.</p>



<a name="168806958"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168806958" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168806958">(Jun 23 2019 at 20:24)</a>:</h4>
<p>And now for backward: <a href="https://perf.rust-lang.org/compare.html?start=a96ba969156d257e5d5b692946fa8fe40ed6543a&amp;end=56b7200c037e2a958f7d907e778b87e58beb7079" target="_blank" title="https://perf.rust-lang.org/compare.html?start=a96ba969156d257e5d5b692946fa8fe40ed6543a&amp;end=56b7200c037e2a958f7d907e778b87e58beb7079">https://perf.rust-lang.org/compare.html?start=a96ba969156d257e5d5b692946fa8fe40ed6543a&amp;end=56b7200c037e2a958f7d907e778b87e58beb7079</a></p>



<a name="168807078"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168807078" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168807078">(Jun 23 2019 at 20:29)</a>:</h4>
<p>Interestingly, <code>deep-vector-opt</code> tops the list for both forwards and backwards ordering, despite containing only a single basic block. I'm thinking maybe it starts with a panic edge for each <code>vec.insert</code> which then gets optimized away?</p>



<a name="168807079"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168807079" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168807079">(Jun 23 2019 at 20:29)</a>:</h4>
<p><a href="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018" target="_blank" title="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018">https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018</a></p>



<a name="168807080"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168807080" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168807080">(Jun 23 2019 at 20:29)</a>:</h4>
<p>There's the source for <code>deep-vector</code></p>



<a name="168807310"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168807310" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168807310">(Jun 23 2019 at 20:36)</a>:</h4>
<p>remember that ordering the blocks in whatever order is also work.</p>



<a name="168807317"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168807317" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168807317">(Jun 23 2019 at 20:37)</a>:</h4>
<p>though little enough of it that I think it does not matter.</p>



<a name="168810095"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168810095" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168810095">(Jun 23 2019 at 22:09)</a>:</h4>
<p>I might try logging the number of dataflow iterations (maybe as a percentage of basic blocks as well). In the backwards case, I expect we're doing about twice as many iterations as we need to, but CFGs are small enough that it doesn't outweigh the overhead from doing an extra traversal in most cases.</p>



<a name="168810141"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168810141" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168810141">(Jun 23 2019 at 22:10)</a>:</h4>
<p>I'll try testing locally.</p>



<a name="168810157"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168810157" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168810157">(Jun 23 2019 at 22:11)</a>:</h4>
<p>Also, how do I print the time taken in each phase of the compiler? Is it granular enough to get time in dataflow?</p>



<a name="168810198"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168810198" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168810198">(Jun 23 2019 at 22:12)</a>:</h4>
<p><code>-Z time-passes</code></p>



<a name="168810200"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168810200" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168810200">(Jun 23 2019 at 22:12)</a>:</h4>
<p><a href="https://forge.rust-lang.org/profile-queries.html" target="_blank" title="https://forge.rust-lang.org/profile-queries.html">https://forge.rust-lang.org/profile-queries.html</a></p>



<a name="168810201"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Iteration%20order%20for%20dataflow/near/168810201" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Iteration.20order.20for.20dataflow.html#168810201">(Jun 23 2019 at 22:12)</a>:</h4>
<p>Found it <span aria-label="smile" class="emoji emoji-263a" role="img" title="smile">:smile:</span></p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>